package com.lyj.sc.dynamicProgramming;

import java.util.Arrays;
import java.util.Stack;

/**
 * @program: code-random
 * @description:
 * @author: lyj
 * @create: 2022-08-28 14:47
 **/
public class dantiaozhan {
    public static int largestRectangleArea(int[] heights) {
        //动态规划
        //单调栈
        //增加头和尾部
        int len = heights.length;
        int[] newHeights = new int[len+2];
        newHeights[0]=0;
        newHeights[len+1]=0;
        for(int i=0;i<len;i++){
            newHeights[i+1]=heights[i];
        }
        heights=newHeights;
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        int res = 0;
        for(int i=1;i<heights.length;i++){
            if(heights[i]>heights[stack.peek()]){
                stack.push(i);
            }else if(heights[i]==heights[stack.peek()]){
                stack.pop();
                stack.push(i);
            }else{
                while(!stack.isEmpty()&&heights[i]<heights[stack.peek()]){
                    System.out.println(stack);
                    int mid = stack.peek();
                    stack.pop();
                    int left=stack.peek();
                    int sum = heights[mid]*(i-left-1);
                    res = Math.max(sum,res);
                }
                stack.push(i);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{2,1,5,6,2,3};
        largestRectangleArea(nums);
    }
}
